package leecode

import "sort"

func combinationSum2LCR(candidates []int, target int) (result [][]int) {
	sort.Ints(candidates)
	path := make([]int, 0)
	used := make([]bool, len(candidates))
	var backtracking func(candidates []int, startIndex int, used []bool)
	backtracking = func(candidates []int, startIndex int, used []bool) {
		//递归终止条件
		if target <= 0 {
			if target == 0 {
				temp := make([]int, len(path))
				copy(temp, path)
				result = append(result, temp)
			}
			return
		}
		for i := startIndex; i < len(candidates); i++ {
			//去重
			if i > 0 && !used[i-1] && candidates[i] == candidates[i-1] {
				continue
			}
			path = append(path, candidates[i])
			used[i] = true
			target = target - candidates[i]
			//递归调用
			backtracking(candidates, i+1, used)
			//回溯
			path = path[:len(path)-1]
			used[i] = false
			target = target + candidates[i]
		}
	}

	backtracking(candidates, 0, used)
	return
}
